package liangtWorkSpace.suanfa;

/**
 * 红皇后问题
 *
 */
public class ReadKing {

    /**
     *
     * @param n
     * @return
     */
    public static int redKing2(int n){
        int[] record = new int[n];
        return process2(record,0,n);
    }

    /**
     *
     * @param record 行坐标
     * @param i 当前行数
     * @param n 总行数
     * @return
     */
    private static int process2(int[] record, int i, int n) {
        if (i == n){
            return 1;
        }
        int res = 0;
        for (int j = 0; j < n; j++) {
            if (isValiad(record,i,j)){
                record[i] = j;
                res +=process2(record,i+1,n);
            }
        }
        return res;
    }

    /**
     * 判断是否新的皇后在旧皇后的线上 如果是则返回false
     * @param record
     * @param i
     * @param j
     * @return
     */
    private static boolean isValiad(int[] record, int i, int j) {
        for (int k = 0; k < i; k++) {
            if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k) ){
                return false;
            }
        }
        return true;
    }

    /**
     * 红皇后问题
     * 公n个皇后摆放在 n * n的棋盘上，，皇后不同行不同列不同线
     *
     * @param a
     * @return
     */
    public static int redKing1(int a){
        if ( a  < 1 || a > 32){
            return 0;
        }
        int limit = a == 32 ? -1:( 1 << a ) - 1;
        return process1(limit,0,0,0);
    }

    /**
     *
     * @param limit 边界
     * @param colLim 执行到的行数
     * @param left 已存在皇后向左偏移存在的位置
     * @param right 已存在皇后向右偏移存在的位置
     * @return
     */
    private static int process1(int limit, int colLim, int left, int right) {
        if (limit == colLim){
            return 1;
        }
        //获取 未使用过的位置节点
        int pos = limit & ( ~(colLim | left | right) );

        int mostRightOne = 0;
        int res = 0;

        while (pos != 0){
            mostRightOne = pos & (~pos +1);
            pos = pos & (~mostRightOne);

            res += process1(limit,
                    colLim|mostRightOne,
                    (left | mostRightOne) << 1,
                    (right | mostRightOne) >>> 1
                    );
        }
        return res;
    }
    /**
     * 红皇后问题
     * 公n个皇后摆放在 n * n的棋盘上，，皇后不同行不同列不同线
     *
     * @param a
     * @return
     */
    public static int redKing3(int a){
        if ( a  < 1 || a > 32){
            return 0;
        }
        int limit = a == 32 ? -1:( 1 << a ) - 1;
        return process3(limit,0,0,0);
    }

    /**
     *
     * @param limit 边界
     * @param colLim 执行到的行数
     * @param left 已存在皇后向左偏移存在的位置
     * @param right 已存在皇后向右偏移存在的位置
     * @return
     */
    private static int process3(int limit, int colLim, int left, int right) {
        if (limit == colLim){
            return 1;
        }
        //获取 未使用过的位置节点
        int pos = limit & ( ~(colLim | left | right) );

        int mostRightOne = 0;
        int res = 0;

        while (pos != 0){
            mostRightOne = pos & (~pos +1);
            pos = pos - mostRightOne;

            res += process1(limit,
                    colLim|mostRightOne,
                    (left | mostRightOne) << 1,
                    (right | mostRightOne) >>> 1
            );
        }
        return res;
    }
    public static void main(String[] args) {
        Long t1 = System.currentTimeMillis();
        System.out.println(redKing1(16));
        Long t2 = System.currentTimeMillis();
        System.out.println("redKing1 = " + (t2-t1));
        t1 = System.currentTimeMillis();
        System.out.println(redKing3(16));
        t2 = System.currentTimeMillis();
        System.out.println("redKing3 = " + (t2-t1));
//        t1 = System.currentTimeMillis();
//        System.out.println(redKing2(7));
//        t2 = System.currentTimeMillis();
//        System.out.println("redKing2 = " + (t2-t1));
    }
}
